package 链表;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class NC51合并k个已排序的链表No23 {

    /**
     * 给你一个链表数组，每个链表都已经按升序排列。
     * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
     *
     * 示例 1：
     * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
     * 输出：[1,1,2,3,4,4,5,6]
     * 解释：链表数组如下：
     * [
     *   1->4->5,
     *   1->3->4,
     *   2->6
     * ]
     * 将它们合并到一个有序链表中得到。
     * 1->1->2->3->4->4->5->6
     * 示例 2：
     * 输入：lists = []
     * 输出：[]
     * 示例 3：
     * 输入：lists = [[]]
     * 输出：[]
     *  
     * 提示：
     * k == lists.length
     * 0 <= k <= 10^4
     * 0 <= lists[i].length <= 500
     * -10^4 <= lists[i][j] <= 10^4
     * lists[i] 按 升序 排列
     * lists[i].length 的总和不超过 10^4
     */

    //堆 但不要一开始全部加入,加入元素越多维护成本越高,应该先加入list.size()个,慢慢吐出,然后再加入
    public ListNode mergeKLists(ArrayList<ListNode> lists) {

        if(lists==null||lists.size()==0){
            return null;
        }

        PriorityQueue<ListNode> priorityQueue=new PriorityQueue<>(Comparator.comparingInt(o -> o.val));

        for (ListNode list : lists) {
            //防止null集合进入堆中导致报错。
            if(list!=null) {
                priorityQueue.add(list);
            }
        }

        ListNode dump=new ListNode();
        ListNode pre=dump;

        while (!priorityQueue.isEmpty()){

            ListNode pollListNode = priorityQueue.poll();
            if(pollListNode.next!=null) {
                priorityQueue.add(pollListNode.next);
            }
            pre.next=pollListNode;
            pre=pre.next;
        }

        return dump.next;
    }

    public static void main(String[] args) {
        NC51合并k个已排序的链表No23 n=new NC51合并k个已排序的链表No23();
        ArrayList<ListNode> list=new ArrayList<>();
        list.add(ListNode.createListNode(new int[]{1,2,3,4,5,6}));
        list.add(null);
        for (ListNode listNode : list) {
            ListNode.printListNode(listNode);
            System.out.println(1);
        }
    }

}
